# 60/100 回溯-分割回文串
# leetcode第131题: https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/14
import json
import time

from leetcode.test import test_function as tf


def partition(s: str) -> list[list[str]]:
    """我的方法"""
    n = len(s)
    res = []

    def back_tracking(path, start, end):
        nonlocal res
        for i in range(end, n + 1):
            # 检查是否是回文串
            if end - start != 1:
                for j in range((end - start) // 2 + 1):
                    if s[start:end][j] != s[start:end][-j - 1]:
                        return
            # 添加到path中
            path.append(s[start:end])
            # path是组成s的完整集合
            if end == n:
                res.append(path[:])
            back_tracking(path, end, i + 1)
            path.pop()

    for i in range(1, n + 1):
        back_tracking([], 0, i)
    return res


def partition_opt(s: str) -> list[list[str]]:
    """优化的方法, 使用动态规划的方法来鉴别是否是回文串"""

    n = len(s)
    dp = [[True] * n for _ in range(n)]

    # 使用dp构建判断是否是回文字符串的集合
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
    res, path = [], []

    def back_tracking(end):
        if end == n:
            res.append(path[:])
            return
        for j in range(end, n):
            if dp[end][j]:
                path.append(s[end:j + 1])
                back_tracking(j + 1)
                path.pop()

    back_tracking(0)
    return res


def partition_ultra(s: str) -> list[list[str]]:
    """代码非常简洁, 但是没看明白, 实测比opt的时间复杂度更高, 因为opt有一些剪枝过程的"""

    dp = [[[]]]
    # dp[i]表示s[:i]所有可能的分割方案
    for i in range(1, len(s) + 1):
        dp.append([])
        for j in range(i):
            tmp = s[j:i]
            if tmp == tmp[::-1]:
                dp[-1].extend(l + [tmp] for l in dp[j])
    return dp[-1]


if __name__ == '__main__':
    with open("../data/j_backtrack7_lc131.data", "r") as file:
        jstr = file.read().strip()
        jo = json.loads(jstr)
    inp = [{"s": "aab"}, {"s": "a"}, {"s": "abaaba"},
           {"s": "abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz"}]
    out = [[["a", "a", "b"], ["aa", "b"]],
           [["a"]],
           [["a", "b", "a", "a", "b", "a", ], ["a", "b", "a", "aba", ], ["a", "b", "aa", "b", "a"], ["a", "baab", "a"],
            ["aba", "a", "b", "a"], ["aba", "aba"], ["abaaba"]],
           jo["ans"]
           ]

    tf(partition, inp, out)

    tf(partition_opt, inp, out)

    # tf(partition_ultra, inp, out)

    # start = time.time()
    # partition_opt("abcdabcdzyxxyzyzvuttuvzyxwxyz")
    # partition_opt("abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # partition_opt("abcdabcdzyxxyzefggfeefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # partition_opt("abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz"
    #               "abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # print(time.time() - start)
    #
    # start = time.time()
    # partition_ultra("abcdabcdzyxxyzyzvuttuvzyxwxyz")
    # partition_ultra("abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # partition_ultra("abcdabcdzyxxyzefggfeefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # partition_ultra("abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz"
    #                 "abcdabcdzyxxyzefgefghkjikjiabccbaijkijklmnopqrssxyzvuttuvzyxwxyz")
    # print(time.time() - start)
